package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1542 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * 经典的状态压缩，一定要学会状态压缩！
     * @return:
     */
    class Solution {
        public int longestAwesome(String s) {
            Map<Integer, Integer> memo = new HashMap<>();
            memo.put(0, -1);

            int status = 0, longestLen = 0;
            for (int i = 0; i < s.length(); i++) {
                int num = s.charAt(i) - '0';
                status = status ^ (1 << num);
                if (memo.containsKey(status)) longestLen = Math.max(longestLen, i - memo.get(status));
                for (int j = 0; j < 10; j++) {
                    int lastStatus = status ^ (1 << j);
                    if (memo.containsKey(lastStatus)) longestLen = Math.max(longestLen, i - memo.get(lastStatus));
                }

                if (!memo.containsKey(status)) memo.put(status, i);
            }

            return longestLen;
        }
    }

    public void run() {
        System.out.println(new Solution().longestAwesome("3242415"));
        System.out.println(new Solution().longestAwesome("12345678"));
        System.out.println(new Solution().longestAwesome("213123"));
        System.out.println(new Solution().longestAwesome("00"));
    }

    public static void main(String[] args) throws Exception {
        LC1542 an = new LC1542();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
